/*
1. 有向图表示：
- 节点：数据类型 
- 边：有向边(节点依赖关系)
- 邻接表：邻接链表
- 邻接矩阵：邻接矩阵
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "topo.h"

// #define HASH_SIZE 128  // 哈希表大小


/*--------- 邻接表 ----------*/
typedef struct QueueNode {
    DataType data;
    struct QueueNode* next;
} QueueNode;

typedef struct {
    QueueNode* front;
    QueueNode* rear;
    int count;              // 队列元素计数
} Queue;


/*---------- 通用工具函数 ----------*/
unsigned int defaultHash(DataType data) {
    return (unsigned int)(long)data;
}

int defaultCompare(DataType a, DataType b) {
    return a == b;
}

/*---------- 队列操作 ----------*/
Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = q->rear = NULL;
    q->count = 0;
    return q;
}

void enqueue(Queue* q, DataType data) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->data = data;
    newNode->next = NULL;

    if (q->rear) {
        q->rear->next = newNode;
        q->rear = newNode;
    } else {
        q->front = q->rear = newNode;
    }
    q->count++;
}

DataType dequeue(Queue* q) {
    if (!q->front) return NULL;

    QueueNode* temp = q->front;
    DataType data = temp->data;

    q->front = q->front->next;
    if (!q->front) q->rear = NULL;
    
    free(temp);
    q->count--;
    return data;
}

int isEmpty(Queue* q) {
    return q->count == 0;
}

/*---------- 图操作 ----------*/
Graph* createGraph(size_t initCapacity, 
                    HashFunc hashFunc, 
                    CompareFunc cmpFunc) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->capacity = initCapacity > 0 ? initCapacity : 16;
    graph->size = 0;
    graph->nodes = (GraphNode*)calloc(graph->capacity, sizeof(GraphNode));
    graph->hashFunc = hashFunc ? hashFunc : defaultHash;
    graph->cmpFunc = cmpFunc ? cmpFunc : defaultCompare;
    return graph;
}

size_t findNodeIndex(const Graph* graph, DataType data) {
    HashType hash = graph->hashFunc(data);
    size_t index = hash % graph->capacity;
    size_t start = index;

    do {
        if (graph->nodes[index].data == NULL || 
            graph->cmpFunc(graph->nodes[index].data, data)) {
            return index;
        }
        index = (index + 1) % graph->capacity;
    } while (index != start);

    return -1;
}

int addNode(Graph* graph, DataType data) {
    size_t index = findNodeIndex(graph, data);
    if (index == -1) return 0;

    if (graph->nodes[index].data == NULL) {
        graph->nodes[index].data = data;
        graph->nodes[index].indegree = 0;
        graph->nodes[index].adjList = NULL;
        graph->size++;
        return 1;
    }
    return 0;
}

int addEdge(Graph* graph, DataType src, DataType dest) {
    size_t srcIndex = findNodeIndex(graph, src);
    size_t destIndex = findNodeIndex(graph, dest);

    if (srcIndex == -1 || destIndex == -1 || 
        !graph->nodes[srcIndex].data || 
        !graph->nodes[destIndex].data) {
        return 0;
    }

    AdjNode* newNode = (AdjNode*)malloc(sizeof(AdjNode));
    newNode->dest = dest;
    newNode->next = graph->nodes[srcIndex].adjList;
    graph->nodes[srcIndex].adjList = newNode;

    graph->nodes[destIndex].indegree++;
    return 1;
}



/*
 * 带批次标记的拓扑排序结果
 * @param taskTab 任务表
 * @param graph 图结构
 * @return 0 成功，-1 图中存在环路
 * @note 结果保存在 TopoResult 结构中，
 *       其中 order 数组保存拓扑排序结果，
 *       batches 数组保存每个任务的批次，
 *       size 保存结果数量，
 *       totalBatches 保存总批次数量。
*/
int topologicalSortWithBatches(const Graph* graph,TopoResult *taskTab) {
    if (graph->size == 0) return -1;

    Queue* q = createQueue();
    DataType* order = (DataType*)malloc(graph->size * sizeof(DataType));
    int* batches = (int*)malloc(graph->size * sizeof(int));
    int* indegrees = (int*)malloc(graph->capacity * sizeof(int));
    size_t count = 0;
    int currentBatch = 0;

    // 初始化入度副本
    for (size_t i = 0; i < graph->capacity; i++) {
        indegrees[i] = graph->nodes[i].indegree;
        if (graph->nodes[i].data && indegrees[i] == 0) {
            enqueue(q, graph->nodes[i].data);
        }
    }

    // 分层处理
    while (!isEmpty(q)) {
        int levelSize = q->count;
        for (int i = 0; i < levelSize; i++) {
            DataType u = dequeue(q);
            order[count] = u;
            batches[count] = currentBatch;
            count++;

            size_t uIndex = findNodeIndex(graph, u);
            if (uIndex == -1) continue;

            // 更新邻接节点入度
            AdjNode* current = graph->nodes[uIndex].adjList;
            while (current) {
                size_t vIndex = findNodeIndex(graph, current->dest);
                if (vIndex != -1 && --indegrees[vIndex] == 0) {
                    enqueue(q, current->dest);
                }
                current = current->next;
            }
        }
        currentBatch++;
    }

    free(indegrees);

    if (count == graph->size) {
        taskTab->order=order;
        taskTab->batches = batches;
        taskTab->size = count;
        taskTab->totalBatches = currentBatch;
    } else {
        free(order);
        free(batches);
    }

    free(q);
    return 0;
}

/*---------- 释放图结构 ----------*/
// 释放图结构内存（安全强化版）
void freeGraph(Graph* graph, FreeFunc freeFunc) {
    if (!graph) return;

    // 安全解引用节点数组
    if (graph->nodes) {
        for (size_t i = 0; i < graph->size; i++) {
            // 明确处理可能为NULL的指针
            GraphNode* current = &graph->nodes[i];
            
            free(current->adjList);    // free() 本身允许NULL指针
            current->adjList = NULL;   // 防御性编程：避免双重释放
            
            // 明确分离函数指针检查
            if (freeFunc && current->data) {
                freeFunc(current->data);
                current->data = NULL;  // 防御性编程
            }
        }
        free(graph->nodes);
        graph->nodes = NULL;  // 标记已释放
    }

    free(graph);
}


/*
---------- 示例使用 ----------
typedef struct {
    char* name;
    int id;
} Task;

unsigned int taskHash(DataType data) {
    Task* t = (Task*)data;
    return t->id * 31;
}

int taskCompare(DataType a, DataType b) {
    Task* t1 = (Task*)a;
    Task* t2 = (Task*)b;
    return t1->id == t2->id;
}

void printTask(DataType data) {
    Task* t = (Task*)data;
    printf("%s(id:%d)", t->name, t->id);
}

int main() {
    // 创建测试任务
    Task tasks[] = {
        {"Initialize", 1},
        {"LoadConfig", 2},
        {"ConnectDB", 3},
        {"StartService", 4},
        {"RunTests", 5},
        {"kkkkkkkkkk",6}
    };

    // 创建图结构
    Graph* graph = createGraph(10, taskHash, taskCompare);
    for (int i = 0; i < 6; i++) {
        addNode(graph, &tasks[i]);
    }

    // 添加依赖关系
    addEdge(graph, &tasks[0], &tasks[1]); // 1->2
    addEdge(graph, &tasks[0], &tasks[2]); // 1->3
    addEdge(graph, &tasks[1], &tasks[3]); // 2->4
    addEdge(graph, &tasks[2], &tasks[3]); // 3->4
    addEdge(graph, &tasks[3], &tasks[4]); // 4->5
    addEdge(graph, &tasks[4], &tasks[5]); // 4->5
    // 执行拓扑排序
    TopoResult result = topologicalSortWithBatches(graph);

    // 输出结果
    if (result.size == 0) {
        printf("图中存在环路！\n");
    } else {
        printf("拓扑排序结果（总批次：%d）:\n", result.totalBatches);
        for (size_t i = 0; i < result.size; i++) {
            printTask(result.order[i]);
            printf(" -> 批次 %d\n", result.batches[i]);
        }
        free(result.order);
        free(result.batches);
    }

    freeGraph(graph, NULL);
    return 0;
}
*/
